from typing import List

# 定义二分查找函数
def search(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    # 先在数组的中间找数值，如果找到了直接返回
    # 当猜测的值不等于下标时，说明猜错了，根据他们的大小关系每次都可以排除掉一半的选项
    while left <= right:
        middle = (left + right) // 2
        if nums[middle] == target:
            return middle
        elif nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

nums1 = [-1,0,3,5,9,12]
target1 = 9

nums2 = [-1,0,3,5,9,12]
target2 = 2

print(search(nums1, target1))
print(search(nums2, target2))
